package com.arithmeticEveryDay.leetCode;

import java.util.Arrays;
import java.util.Scanner;

/*

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。 

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

 

示例 1：

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：

输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0
示例 3：

输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1
 

提示：

n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] == 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
initial 中所有整数均不重复

3
1 1 0
1 1 0
0 0 1
3
0 1 2

4
1 0 0 0
0 1 0 0
0 0 1 1
0 0 1 1
2
3 1

11
1 0 0 0 0 0 0 0 0 0 1
0 1 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 1 0 0 1 1 0
0 0 0 0 0 0 1 1 0 0 0
0 0 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 1
5
7 8 6 2 3

 */
public class Solution924 {
    
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int m = initial.length;
        DisjointSet924 set = new DisjointSet924(n);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (graph[i][j] == 1) {
                    int iRoot = set.findRoot(i);
                    int jRoot = set.findRoot(j);
                    set.union(iRoot, jRoot);
                }
            }
        }
        System.out.println(Arrays.toString(set.parent));
        System.out.println(Arrays.toString(set.size));
        
        // 得到初始状态被感染结点的连通块中有多少被感染结点
        for (int i = 0; i < m; i++) {
            int iRoot = set.findRoot(initial[i]);
            set.count[iRoot]++;
        }
        
        System.out.println(Arrays.toString(set.count));
        // 索引从小到大排序，因为答案要求，如果所有结点解救效果都一样，返回最小的那个索引
        Arrays.sort(initial);
        // 如果初始状态被感染结点的连通块中只有一个被感染结点，
        // 那么救下这个一个被感染的结点就能救下和它连通的整个连通块中的全部结点
        // 最大可解救结点数
        int maxRescue = -1;
        // 具有最大可解救结点数的结点
        int maxRescueI = initial[0];
        for (int i = 0; i < m; i++) {
            int iRoot = set.findRoot(initial[i]);
            if (set.count[iRoot] == 1 && set.size[iRoot] > maxRescue) {
                maxRescueI = initial[i];
                maxRescue = set.size[iRoot];
            }
        }
        return maxRescueI;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = scan.nextInt();
            }
        }
        int m = scan.nextInt();
        int[] initial = new int[m];
        for (int i = 0; i < m; i++) {
            initial[i] = scan.nextInt();
        }
        Solution924 s = new Solution924();
        System.out.println(s.minMalwareSpread(graph, initial));
        
    }

}
class DisjointSet924 {
    int[] parent;
    int[] size;
    int[] count;
    
    public DisjointSet924(int n) {
        parent = new int[n];
        size = new int[n];
        count = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int findRoot(int i) {
        if (parent[i] == i) {
            return i;
        } else {
            parent[i] = findRoot(parent[i]);
            return parent[i];
        }
    }
    
    public void union(int i, int j) {
        if (size[i] >= size[j]) {
            parent[j] = i;
            size[i]++;
        } else {
            parent[i] = j;
            size[j]++;
        }
    }
}

